<!-- HTML header for doxygen 1.8.6-->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.13"/>
<title>OpenCV: Feature Matching</title>
<link href="../../opencv.ico" rel="shortcut icon" type="image/x-icon" />
<link href="../../tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="../../jquery.js"></script>
<script type="text/javascript" src="../../dynsections.js"></script>
<script type="text/javascript" src="../../tutorial-utils.js"></script>
<link href="../../search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="../../search/searchdata.js"></script>
<script type="text/javascript" src="../../search/search.js"></script>
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    extensions: ["tex2jax.js", "TeX/AMSmath.js", "TeX/AMSsymbols.js"],
    jax: ["input/TeX","output/HTML-CSS"],
});
//<![CDATA[
MathJax.Hub.Config(
{
  TeX: {
      Macros: {
          matTT: [ "\\[ \\left|\\begin{array}{ccc} #1 & #2 & #3\\\\ #4 & #5 & #6\\\\ #7 & #8 & #9 \\end{array}\\right| \\]", 9],
          fork: ["\\left\\{ \\begin{array}{l l} #1 & \\mbox{#2}\\\\ #3 & \\mbox{#4}\\\\ \\end{array} \\right.", 4],
          forkthree: ["\\left\\{ \\begin{array}{l l} #1 & \\mbox{#2}\\\\ #3 & \\mbox{#4}\\\\ #5 & \\mbox{#6}\\\\ \\end{array} \\right.", 6],
          forkfour: ["\\left\\{ \\begin{array}{l l} #1 & \\mbox{#2}\\\\ #3 & \\mbox{#4}\\\\ #5 & \\mbox{#6}\\\\ #7 & \\mbox{#8}\\\\ \\end{array} \\right.", 8],
          vecthree: ["\\begin{bmatrix} #1\\\\ #2\\\\ #3 \\end{bmatrix}", 3],
          vecthreethree: ["\\begin{bmatrix} #1 & #2 & #3\\\\ #4 & #5 & #6\\\\ #7 & #8 & #9 \\end{bmatrix}", 9],
          cameramatrix: ["#1 = \\begin{bmatrix} f_x & 0 & c_x\\\\ 0 & f_y & c_y\\\\ 0 & 0 & 1 \\end{bmatrix}", 1],
          distcoeffs: ["(k_1, k_2, p_1, p_2[, k_3[, k_4, k_5, k_6 [, s_1, s_2, s_3, s_4[, \\tau_x, \\tau_y]]]]) \\text{ of 4, 5, 8, 12 or 14 elements}"],
          distcoeffsfisheye: ["(k_1, k_2, k_3, k_4)"],
          hdotsfor: ["\\dots", 1],
          mathbbm: ["\\mathbb{#1}", 1],
          bordermatrix: ["\\matrix{#1}", 1]
      }
  }
}
);
//]]>
</script><script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js"></script>
<link href="../../doxygen.css" rel="stylesheet" type="text/css" />
<link href="../../stylesheet.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<!--#include virtual="/google-search.html"-->
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectlogo"><img alt="Logo" src="../../opencv-logo-small.png"/></td>
  <td style="padding-left: 0.5em;">
   <div id="projectname">OpenCV
   &#160;<span id="projectnumber">4.5.2</span>
   </div>
   <div id="projectbrief">Open Source Computer Vision</div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.13 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "../../search",false,'Search');
</script>
<script type="text/javascript" src="../../menudata.js"></script>
<script type="text/javascript" src="../../menu.js"></script>
<script type="text/javascript">
$(function() {
  initMenu('../../',true,false,'search.php','Search');
  $(document).ready(function() { init_search(); });
});
</script>
<div id="main-nav"></div>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div id="nav-path" class="navpath">
  <ul>
<li class="navelem"><a class="el" href="../../d6/d00/tutorial_py_root.html">OpenCV-Python Tutorials</a></li><li class="navelem"><a class="el" href="../../db/d27/tutorial_py_table_of_contents_feature2d.html">Feature Detection and Description</a></li>  </ul>
</div>
</div><!-- top -->
<div class="header">
  <div class="headertitle">
<div class="title">Feature Matching </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><h2>Goal </h2>
<p>In this chapter</p><ul>
<li>We will see how to match features in one image with others.</li>
<li>We will use the Brute-Force matcher and FLANN Matcher in OpenCV</li>
</ul>
<h2>Basics of Brute-Force Matcher </h2>
<p>Brute-Force matcher is simple. It takes the descriptor of one feature in first set and is matched with all other features in second set using some distance calculation. And the closest one is returned.</p>
<p>For BF matcher, first we have to create the BFMatcher object using <b><a class="el" href="../../d3/da1/classcv_1_1BFMatcher.html" title="Brute-force descriptor matcher. ">cv.BFMatcher()</a></b>. It takes two optional params. First one is normType. It specifies the distance measurement to be used. By default, it is <a class="el" href="../../d2/de8/group__core__array.html#ggad12cefbcb5291cf958a85b4b67b6149fa7bacbe84d400336a8f26297d8e80e3a2">cv.NORM_L2</a>. It is good for SIFT, SURF etc (<a class="el" href="../../d2/de8/group__core__array.html#ggad12cefbcb5291cf958a85b4b67b6149fab55c78ff204a979026c026ea19de65c9">cv.NORM_L1</a> is also there). For binary string based descriptors like ORB, BRIEF, BRISK etc, <a class="el" href="../../d2/de8/group__core__array.html#ggad12cefbcb5291cf958a85b4b67b6149fa4b063afd04aebb8dd07085a1207da727">cv.NORM_HAMMING</a> should be used, which used Hamming distance as measurement. If ORB is using WTA_K == 3 or 4, <a class="el" href="../../d2/de8/group__core__array.html#ggad12cefbcb5291cf958a85b4b67b6149fa7fab9cda83e79380cd273c49de8e3231">cv.NORM_HAMMING2</a> should be used.</p>
<p>Second param is boolean variable, crossCheck which is false by default. If it is true, Matcher returns only those matches with value (i,j) such that i-th descriptor in set A has j-th descriptor in set B as the best match and vice-versa. That is, the two features in both sets should match each other. It provides consistent result, and is a good alternative to ratio test proposed by D.Lowe in SIFT paper.</p>
<p>Once it is created, two important methods are <em>BFMatcher.match()</em> and <em>BFMatcher.knnMatch()</em>. First one returns the best match. Second method returns k best matches where k is specified by the user. It may be useful when we need to do additional work on that.</p>
<p>Like we used <a class="el" href="../../d4/d5d/group__features2d__draw.html#ga5d2bafe8c1c45289bc3403a40fb88920" title="Draws keypoints. ">cv.drawKeypoints()</a> to draw keypoints, <b><a class="el" href="../../d4/d5d/group__features2d__draw.html#gad8f463ccaf0dc6f61083abd8717c261a" title="Draws the found matches of keypoints from two images. ">cv.drawMatches()</a></b> helps us to draw the matches. It stacks two images horizontally and draw lines from first image to second image showing best matches. There is also <b>cv.drawMatchesKnn</b> which draws all the k best matches. If k=2, it will draw two match-lines for each keypoint. So we have to pass a mask if we want to selectively draw it.</p>
<p>Let's see one example for each of SIFT and ORB (Both use different distance measurements).</p>
<h3>Brute-Force Matching with ORB Descriptors</h3>
<p>Here, we will see a simple example on how to match features between two images. In this case, I have a queryImage and a trainImage. We will try to find the queryImage in trainImage using feature matching. ( The images are /samples/data/box.png and /samples/data/box_in_scene.png)</p>
<p>We are using ORB descriptors to match features. So let's start with loading images, finding descriptors etc. </p><div class="fragment"><div class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</div><div class="line"><span class="keyword">import</span> cv2 <span class="keyword">as</span> cv</div><div class="line"><span class="keyword">import</span> matplotlib.pyplot <span class="keyword">as</span> plt</div><div class="line"></div><div class="line">img1 = <a class="code" href="../../d4/da8/group__imgcodecs.html#ga288b8b3da0892bd651fce07b3bbd3a56">cv.imread</a>(<span class="stringliteral">&#39;box.png&#39;</span>,cv.IMREAD_GRAYSCALE)          <span class="comment"># queryImage</span></div><div class="line">img2 = <a class="code" href="../../d4/da8/group__imgcodecs.html#ga288b8b3da0892bd651fce07b3bbd3a56">cv.imread</a>(<span class="stringliteral">&#39;box_in_scene.png&#39;</span>,cv.IMREAD_GRAYSCALE) <span class="comment"># trainImage</span></div><div class="line"></div><div class="line"><span class="comment"># Initiate ORB detector</span></div><div class="line">orb = cv.ORB_create()</div><div class="line"></div><div class="line"><span class="comment"># find the keypoints and descriptors with ORB</span></div><div class="line">kp1, des1 = orb.detectAndCompute(img1,<span class="keywordtype">None</span>)</div><div class="line">kp2, des2 = orb.detectAndCompute(img2,<span class="keywordtype">None</span>)</div></div><!-- fragment --><p> Next we create a BFMatcher object with distance measurement <a class="el" href="../../d2/de8/group__core__array.html#ggad12cefbcb5291cf958a85b4b67b6149fa4b063afd04aebb8dd07085a1207da727">cv.NORM_HAMMING</a> (since we are using ORB) and crossCheck is switched on for better results. Then we use Matcher.match() method to get the best matches in two images. We sort them in ascending order of their distances so that best matches (with low distance) come to front. Then we draw only first 10 matches (Just for sake of visibility. You can increase it as you like) </p><div class="fragment"><div class="line"><span class="comment"># create BFMatcher object</span></div><div class="line">bf = <a class="code" href="../../d3/da1/classcv_1_1BFMatcher.html">cv.BFMatcher</a>(cv.NORM_HAMMING, crossCheck=<span class="keyword">True</span>)</div><div class="line"></div><div class="line"><span class="comment"># Match descriptors.</span></div><div class="line">matches = bf.match(des1,des2)</div><div class="line"></div><div class="line"><span class="comment"># Sort them in the order of their distance.</span></div><div class="line">matches = sorted(matches, key = <span class="keyword">lambda</span> x:x.distance)</div><div class="line"></div><div class="line"><span class="comment"># Draw first 10 matches.</span></div><div class="line">img3 = <a class="code" href="../../d4/d5d/group__features2d__draw.html#ga62fbedb5206ab2faf411797e7055c90f">cv.drawMatches</a>(img1,kp1,img2,kp2,matches[:10],<span class="keywordtype">None</span>,flags=cv.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS)</div><div class="line"></div><div class="line">plt.imshow(img3),plt.show()</div></div><!-- fragment --><p> Below is the result I got:</p>
<div class="image">
<img src="../../matcher_result1.jpg" alt="matcher_result1.jpg"/>
<div class="caption">
image</div></div>
 <h3>What is this Matcher Object?</h3>
<p>The result of matches = bf.match(des1,des2) line is a list of DMatch objects. This DMatch object has following attributes:</p>
<ul>
<li>DMatch.distance - Distance between descriptors. The lower, the better it is.</li>
<li>DMatch.trainIdx - Index of the descriptor in train descriptors</li>
<li>DMatch.queryIdx - Index of the descriptor in query descriptors</li>
<li>DMatch.imgIdx - Index of the train image.</li>
</ul>
<h3>Brute-Force Matching with SIFT Descriptors and Ratio Test</h3>
<p>This time, we will use BFMatcher.knnMatch() to get k best matches. In this example, we will take k=2 so that we can apply ratio test explained by D.Lowe in his paper. </p><div class="fragment"><div class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</div><div class="line"><span class="keyword">import</span> cv2 <span class="keyword">as</span> cv</div><div class="line"><span class="keyword">import</span> matplotlib.pyplot <span class="keyword">as</span> plt</div><div class="line"></div><div class="line">img1 = <a class="code" href="../../d4/da8/group__imgcodecs.html#ga288b8b3da0892bd651fce07b3bbd3a56">cv.imread</a>(<span class="stringliteral">&#39;box.png&#39;</span>,cv.IMREAD_GRAYSCALE)          <span class="comment"># queryImage</span></div><div class="line">img2 = <a class="code" href="../../d4/da8/group__imgcodecs.html#ga288b8b3da0892bd651fce07b3bbd3a56">cv.imread</a>(<span class="stringliteral">&#39;box_in_scene.png&#39;</span>,cv.IMREAD_GRAYSCALE) <span class="comment"># trainImage</span></div><div class="line"></div><div class="line"><span class="comment"># Initiate SIFT detector</span></div><div class="line">sift = cv.SIFT_create()</div><div class="line"></div><div class="line"><span class="comment"># find the keypoints and descriptors with SIFT</span></div><div class="line">kp1, des1 = sift.detectAndCompute(img1,<span class="keywordtype">None</span>)</div><div class="line">kp2, des2 = sift.detectAndCompute(img2,<span class="keywordtype">None</span>)</div><div class="line"></div><div class="line"><span class="comment"># BFMatcher with default params</span></div><div class="line">bf = <a class="code" href="../../d3/da1/classcv_1_1BFMatcher.html">cv.BFMatcher</a>()</div><div class="line">matches = bf.knnMatch(des1,des2,k=2)</div><div class="line"></div><div class="line"><span class="comment"># Apply ratio test</span></div><div class="line">good = []</div><div class="line"><span class="keywordflow">for</span> m,n <span class="keywordflow">in</span> matches:</div><div class="line">    <span class="keywordflow">if</span> m.distance &lt; 0.75*n.distance:</div><div class="line">        good.append([m])</div><div class="line"></div><div class="line"><span class="comment"># cv.drawMatchesKnn expects list of lists as matches.</span></div><div class="line">img3 = cv.drawMatchesKnn(img1,kp1,img2,kp2,good,<span class="keywordtype">None</span>,flags=cv.DrawMatchesFlags_NOT_DRAW_SINGLE_POINTS)</div><div class="line"></div><div class="line">plt.imshow(img3),plt.show()</div></div><!-- fragment --><p> See the result below:</p>
<div class="image">
<img src="../../matcher_result2.jpg" alt="matcher_result2.jpg"/>
<div class="caption">
image</div></div>
 <h2>FLANN based Matcher </h2>
<p>FLANN stands for Fast Library for Approximate Nearest Neighbors. It contains a collection of algorithms optimized for fast nearest neighbor search in large datasets and for high dimensional features. It works faster than BFMatcher for large datasets. We will see the second example with FLANN based matcher.</p>
<p>For FLANN based matcher, we need to pass two dictionaries which specifies the algorithm to be used, its related parameters etc. First one is IndexParams. For various algorithms, the information to be passed is explained in FLANN docs. As a summary, for algorithms like SIFT, SURF etc. you can pass following: </p><div class="fragment"><div class="line">FLANN_INDEX_KDTREE = 1</div><div class="line">index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)</div></div><!-- fragment --><p> While using ORB, you can pass the following. The commented values are recommended as per the docs, but it didn't provide required results in some cases. Other values worked fine.: </p><div class="fragment"><div class="line">FLANN_INDEX_LSH = 6</div><div class="line">index_params= dict(algorithm = FLANN_INDEX_LSH,</div><div class="line">                   table_number = 6, <span class="comment"># 12</span></div><div class="line">                   key_size = 12,     <span class="comment"># 20</span></div><div class="line">                   multi_probe_level = 1) <span class="comment">#2</span></div></div><!-- fragment --><p> Second dictionary is the SearchParams. It specifies the number of times the trees in the index should be recursively traversed. Higher values gives better precision, but also takes more time. If you want to change the value, pass search_params = dict(checks=100).</p>
<p>With this information, we are good to go. </p><div class="fragment"><div class="line"><span class="keyword">import</span> numpy <span class="keyword">as</span> np</div><div class="line"><span class="keyword">import</span> cv2 <span class="keyword">as</span> cv</div><div class="line"><span class="keyword">import</span> matplotlib.pyplot <span class="keyword">as</span> plt</div><div class="line"></div><div class="line">img1 = <a class="code" href="../../d4/da8/group__imgcodecs.html#ga288b8b3da0892bd651fce07b3bbd3a56">cv.imread</a>(<span class="stringliteral">&#39;box.png&#39;</span>,cv.IMREAD_GRAYSCALE)          <span class="comment"># queryImage</span></div><div class="line">img2 = <a class="code" href="../../d4/da8/group__imgcodecs.html#ga288b8b3da0892bd651fce07b3bbd3a56">cv.imread</a>(<span class="stringliteral">&#39;box_in_scene.png&#39;</span>,cv.IMREAD_GRAYSCALE) <span class="comment"># trainImage</span></div><div class="line"></div><div class="line"><span class="comment"># Initiate SIFT detector</span></div><div class="line">sift = cv.SIFT_create()</div><div class="line"></div><div class="line"><span class="comment"># find the keypoints and descriptors with SIFT</span></div><div class="line">kp1, des1 = sift.detectAndCompute(img1,<span class="keywordtype">None</span>)</div><div class="line">kp2, des2 = sift.detectAndCompute(img2,<span class="keywordtype">None</span>)</div><div class="line"></div><div class="line"><span class="comment"># FLANN parameters</span></div><div class="line">FLANN_INDEX_KDTREE = 1</div><div class="line">index_params = dict(algorithm = FLANN_INDEX_KDTREE, trees = 5)</div><div class="line">search_params = dict(checks=50)   <span class="comment"># or pass empty dictionary</span></div><div class="line"></div><div class="line">flann = <a class="code" href="../../dc/de2/classcv_1_1FlannBasedMatcher.html">cv.FlannBasedMatcher</a>(index_params,search_params)</div><div class="line"></div><div class="line">matches = flann.knnMatch(des1,des2,k=2)</div><div class="line"></div><div class="line"><span class="comment"># Need to draw only good matches, so create a mask</span></div><div class="line">matchesMask = [[0,0] <span class="keywordflow">for</span> i <span class="keywordflow">in</span> range(len(matches))]</div><div class="line"></div><div class="line"><span class="comment"># ratio test as per Lowe&#39;s paper</span></div><div class="line"><span class="keywordflow">for</span> i,(m,n) <span class="keywordflow">in</span> enumerate(matches):</div><div class="line">    <span class="keywordflow">if</span> m.distance &lt; 0.7*n.distance:</div><div class="line">        matchesMask[i]=[1,0]</div><div class="line"></div><div class="line">draw_params = dict(matchColor = (0,255,0),</div><div class="line">                   singlePointColor = (255,0,0),</div><div class="line">                   matchesMask = matchesMask,</div><div class="line">                   flags = cv.DrawMatchesFlags_DEFAULT)</div><div class="line"></div><div class="line">img3 = cv.drawMatchesKnn(img1,kp1,img2,kp2,matches,<span class="keywordtype">None</span>,**draw_params)</div><div class="line"></div><div class="line">plt.imshow(img3,),plt.show()</div></div><!-- fragment --><p> See the result below:</p>
<div class="image">
<img src="../../matcher_flann.jpg" alt="matcher_flann.jpg"/>
<div class="caption">
image</div></div>
 <h2>Additional Resources </h2>
<h2>Exercises </h2>
</div></div><!-- contents -->
<!-- HTML footer for doxygen 1.8.6-->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated on Fri Apr 2 2021 11:36:37 for OpenCV by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="../../doxygen.png" alt="doxygen"/>
</a> 1.8.13
</small></address>
<script type="text/javascript">
//<![CDATA[
addTutorialsButtons();
//]]>
</script>
</body>
</html>
